// 递归搜索与回溯 - 决策树问题
// 当一个题目可以使用决策树画出来，那么也可以通过递归的方法解决
// 画决策树，要保证不重不漏
// 使用全局变量进行统计，避免递归函数头传参问题
// 设计递归函数头，是否需要记录本次决策的位置，层数，个数等信息
// 回溯时注意本层计算完成后，直接在本层回溯，返回上一个位置

// 例题 2：
// 给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
//
//        解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
//
//        示例 1：
//
//        输入：nums = [1,2,3]
//        输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
//        示例 2：
//
//        输入：nums = [0]
//        输出：[[],[0]]
//
//
//        提示：
//
//        1 <= nums.length <= 10
//        -10 <= nums[i] <= 10
//        nums 中的所有元素 互不相同

// 解题思路 1：
// 数组中的元素，每一个元素可以选，也可以不选，根据这个思路，画决策树
// 画出来的决策树是一个二叉树
// 二叉树可以先搞一搞左树，再搞一搞右树
// 注意如果在本层选了元素，那么恢复现场的时候要注意在本层清除元素
// 返回上一层前就已经清除完毕了
// 收集二叉树所有的叶子节点，每一个叶子节点都是符合要求的子集

// 解题思路 2：
// 考虑选择数组中元素的数量，选 1个，2个，3个... ，根据这个思路画决策树
// 如果选 0 个，就是空集
// 设计函数头，传一个变量记录数量，表示到本层要选第几个元素
// 每一个节点都是符合要求的子集，进入递归后，可以先收集结果
// 选完某一个元素后，再选就需要从该元素后面的元素中进行选择，避免重复

import java.util.ArrayList;
import java.util.List;

public class Subsets {
    List<List<Integer>> ret;
    List<Integer> path;
    public List<List<Integer>> subsets1(int[] nums) {
        int n = nums.length;
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs1(nums, 0);
        return ret;
    }
    public void dfs1(int[] nums, int pos){
        if(pos >= nums.length){
            ret.add(new ArrayList<>(path));
            return;
        }
        dfs1(nums, pos + 1);
        path.add(nums[pos]);
        dfs1(nums, pos + 1);
        path.remove(path.size() - 1);
    }

    public List<List<Integer>> subsets2(int[] nums) {
        int n = nums.length;
        ret = new ArrayList<>();
        path = new ArrayList<>();
        dfs2(nums, 0);
        return ret;
    }
    public void dfs2(int[] nums, int pos){
        ret.add(new ArrayList<>(path));
        for(int i = pos; i < nums.length; i++){
            path.add(nums[i]);
            dfs2(nums, i + 1);
            path.remove(path.size() - 1);
        }
    }
}
